package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC788 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 动态规划的解法，第一个参数i表示原数的第几位，比如i=0就表示第1位(最高位）dp[0]就等于若干个dp[1]的数之和，
     * dp[1]等于若干个dp[2]的数之和，第二个参数equality_flag表示i之前的所有位数是否达到最大值，比如'1234'，我们现在在'3'这个位置，
     * 如果equality_flag==true的话说明前缀都到达最大数了，也就是前面的数已经是'12'了，下一个数只能在range(3+1)里面取，
     * 而假如前面是'11'的话，下一个数是可以在range(10)里面取的，第3个参数表示已有的数字里是否有'2569'
     * 状态可以表示为三个变量 i, equality_flag, involution_flag。其中 i 表示当前正在写第 i 位数字；
     * equality_flag 表示已经写出的 j 位数字是否等于 N 的 j 位前缀；
     * involution_flag 表示从最高位到比当前位高一位的这段前缀中是否含有 2569 中的任意一个数字。
        dp(i, equality_flag, involution_flag) 表示在特定 equality_flag，involution_flag 的状态下，
        * 有多少种从 i 到末尾的后缀能组成一个好数。最终的结果为 dp(0, True, False)。
        注：数字 N 从最高位到最低位的索引，从 0 开始，并依次增大。第 i 位表示索引为 i 的位置。
     * @return:
     */
    class Solution {
        public int rotatedDigits(int N) {
            char[] A = String.valueOf(N).toCharArray();
            int K = A.length;

            int[][][] memo = new int[K + 1][2][2];
            memo[K][0][1] = memo[K][1][1] = 1;
            for (int i = K - 1; i >= 0; --i) {
                for (int eqf = 0; eqf <= 1; ++eqf)
                    for (int invf = 0; invf <= 1; ++invf) {
                        // We will compute ans = memo[i][eqf][invf],
                        // the number of good numbers with respect to N = A[i:].
                        // If eqf is true, we must stay below N, otherwise
                        // we can use any digits.
                        // Invf becomes true when we write a 2569, and it
                        // must be true by the end of our writing as all
                        // good numbers have a digit in 2569.
                        int ans = 0;
                        for (char d = '0'; d <= (eqf == 1 ? A[i] : '9'); ++d) {
                            if (d == '3' || d == '4' || d == '7') continue;
                            boolean invo = (d == '2' || d == '5' || d == '6' || d == '9');
                            ans += memo[i + 1][d == A[i] ? eqf : 0][invo ? 1 : invf];
                        }
                        memo[i][eqf][invf] = ans;
                    }
            }

            return memo[0][1][0];
        }

    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC788 an = new LC788();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
